Konversi Postfiks ke Prefiks

Tujuan

Tujuan Anda adalah mengonversi sebuah ekspresi postfiks (Notasi Polandia Terbalik) menjadi ekspresi yang setara ekspresi prefiks (Notasi Polandia) dengan membangun dan menelusuri pohon ekspresi.

Algoritma

1. Bangun Pohon Ekspresi: Proses ekspresi postfiks dari kiri ke kanan menggunakan tumpukan.
   • Ketika ditemukan operand (misalnya A, B), buat pohon satu simpul untuk operand tersebut dan masukkan ke dalam tumpukan.
   • Ketika ditemukan operator (misalnya +, *) ditemukan, ambil dua pohon dari tumpukan. Yang pertama diambil adalah anak kanan (T₂) dan yang kedua adalah anak kiri (T₁). Buat pohon baru dengan operator sebagai akar dan kembalikan ke dalam tumpukan.
2. Hasilkan String Prefiks: Setelah memproses semua token, tumpukan akan menyimpan pohon ekspresi lengkap. Lakukan penelusuran preorder (Akar → Kiri → Kanan) pada pohon ini untuk menghasilkan ekspresi prefiks akhir.

Contoh

Untuk ekspresi postfiks A B + C *, algoritma membangun pohon berikut:

  *
   / \
  +   C
 / \
A   B

Penelusuran preorder menghasilkan ekspresi prefiks: * + A B C.

Format Masukan/Keluaran

Masukan

• Baris 1: Sebuah bilangan bulat N (1 ≤ N ≤ 1000), jumlah token.
• Baris 2: Ekspresi postfiks, dengan N token dipisahkan oleh spasi.

Aturan Token

• Operand: Huruf kapital tunggal (A-Z).
• Operator: Empat operator biner: +, -, *, /.

Keluaran

• Satu baris yang berisi ekspresi prefiks yang sesuai, dengan token dipisahkan oleh spasi.

Contoh

Contoh 1:

5

A B + C *

* + A B C

Contoh 2:

7

A B C * + D /

/ + A * B C D

Contoh 3:

7

A B + C D - *

* + A B - C D

Batasan